package com.ds.linked;

public class MyLinked {

	private static class Node {
		public Object data;  //数据域
		public Node next;  //后继指针域
	}

	//链表的头结点
	private Node head = new Node();

	//创建一个节点类型变量，用来指向链表的最后一个节点
	private Node lastNode = head;  //初始状态下，这个变量直接指向链表的头结点

	//创建一个变量，用来记录当前链表中已经存在的节点数量
	private int size = 0;

	/**
	 * 向链表的结尾添加元素的方法
	 * @param data 加入链表的元素
	 */
	public void add(Object data) {

		//[1]创建一个新节点，用来保存加入链表的数据
		Node node = new Node();
		node.data = data;

		//[2]将新节点挂在最后一个节点的末尾
		lastNode.next = node;

		//[3]lastNode变量指向这个节点
		lastNode = node;

		//[4]节点数量+1
		size++;

	}

	/**
	 * 向链表的制定下标插入元素的方法
	 * @param index 指定的元素下标
	 * @param data 新的数据
	 */
	public void add(int index, Object data) {

		//[1]首先判断下，用户指定插入的节点下标是不是超过了最大节点数量，如果是，那么直接使用追加的方式添加节点
		if(index >= size) {
			add(data);
			return;  //方法结束
		}

		//-----走到这一步，说明用户指定添加元素的下标，并没有超过最大元素数量，使用插入的方式将节点添加到链表中-----

		//[2]使用一个新节点保存新元素
		Node node = new Node();
		node.data = data;

		//[3]创建一个计步器变量，用来记录从链表头结点开始已经访问了多少个节点
		int step = 0;

		//[4]从链表的头结点开始，一个节点一个节点的向后查找并计步，直到找到插入为止之前的一个节点为止
		Node current = head;  //使用一个节点型变量，用来指示当前遍历到的节点
		while(step < index) {
			current = current.next;  //遍历下一个节点
			step++;  //计步器自增
		}

		//[5]将新节点插入到指定的下标位上
		node.next = current.next;
		current.next = node;
		size++;

	}

	/**
	 * 遍历链表的方法
	 */
	public void iterate() {

		//[0]整个遍历的前提条件是链表中存在元素
		if(size > 0) {
			//[1]创建一个临时变量，用来标记当前正在遍历的节点
			Node current = head.next;  //最开始这个变量指向链表头的下一个节点，也就是真正保存数据的第一个节点

			//[2]使用循环遍历整个数组，边遍历边打印
			System.out.print("[");
			while(current != null) {
				System.out.print(current.data + " ");
				current = current.next;
			}
			System.out.print("]");
		}

	}

	public static void main(String[] args) {

		MyLinked ml = new MyLinked();

		ml.add("a");
		ml.add("b");
		ml.add("c");
		ml.add("d");
		ml.add("e");

		ml.add(0, "f");
		ml.add(2, "g");
		ml.add(100, "h");

		ml.iterate();

	}

}
